#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<unordered_set>

using namespace std;


long long countGoodIntegers(int n, int k) {
    vector<int> f(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++)
        f[i] = f[i - 1] * i;

    long long ans = 0;
    unordered_set<string> vis;
    int base = pow(10, (n - 1) / 2);
    for (int i = base; i < base * 10; i++)
    {
        string s = to_string(i);
        s += string(s.rbegin() + (n % 2), s.rend());
        if (stoll(s) % k)
            continue;
        ranges::sort(s);
        if (!vis.insert(s).second)
            continue;

        int cnt[10]{};
        for (auto c : s)
            cnt[c - '0']++;

        int res = (n - cnt[0]) * f[n - 1];
        for (auto c : cnt)
            res /= f[c];
        ans += res;
    }
    return ans;
}